//给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的
//唯一组合。 
//
// candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。 
//
// 对于给定的输入，保证和为 target 的唯一组合数少于 150 个。 
//
// 
//
// 示例 1： 
//
// 
//输入: candidates = [2,3,6,7], target = 7
//输出: [[7],[2,2,3]]
// 
//
// 示例 2： 
//
// 
//输入: candidates = [2,3,5], target = 8
//输出: [[2,2,2,2],[2,3,3],[3,5]] 
//
// 示例 3： 
//
// 
//输入: candidates = [2], target = 1
//输出: []
// 
//
// 示例 4： 
//
// 
//输入: candidates = [1], target = 1
//输出: [[1]]
// 
//
// 示例 5： 
//
// 
//输入: candidates = [1], target = 2
//输出: [[1,1]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= candidates.length <= 30 
// 1 <= candidates[i] <= 200 
// candidate 中的每个元素都是独一无二的。 
// 1 <= target <= 500 
// 
// Related Topics 数组 回溯 
// 👍 1470 👎 0

package leetcode.editor.cn;

import common.util.MyUtil;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * Java：组合总和
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P39_CombinationSum {
    public static void main(String[] args) {
        Solution solution = new P39_CombinationSum().new Solution();
        int[] candidates = MyUtil.createArray(2, 3, 5);
        int targer = 8;
        MyUtil.printJson(solution.combinationSum(candidates, targer));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            if (candidates == null || candidates.length == 0) {
                return null;
            }
            int min = Integer.MAX_VALUE;
            for (int n : candidates) {
                min = Math.min(min, n);
            }
            // 最多的元素个数 target/min + 1
            int maxLength = target / min + 1;

            Set<List<Integer>> res = new HashSet<>();
            process(candidates, 0, 0, target, 0, new int[maxLength], res);
            return new ArrayList<>(res);
        }

        public void process(int[] arr, int cur, int sum, int target, int times, int[] path, Set<List<Integer>> res) {
            if (sum == target) {
                res.add(depth(path));
                return;
            }
            if (sum > target || cur == arr.length) {
                return;
            }

            // 不选择当前元素
            process(arr, cur + 1, sum, target, times, path, res);

            // 选择当前元素
            path[times] = arr[cur];
            process(arr, cur, sum + arr[cur], target, times + 1, path, res);
            path[times] = 0;

        }

        private List<Integer> depth(int[] path) {
            List<Integer> res = new ArrayList<>();
            for (int n : path) {
                if (n != 0) {
                    res.add(n);
                }
            }
            //res.sort((a, b) -> a - b);
            return res;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}